/*
	假设一个整数序列采用向量容器v存放，
	设计一个尽可能高效的算法删除v中所有的奇数元素，
	要求删除后v中元素的相对次序保持不变。
*/

#include<iostream>
#include<vector>
using namespace std;

// 整体建表法
void delodd1(vector<int>&v)
{
	// 记录下一个元素的插放位置
	int k=0;	
	int i=0;
	while(i<v.size())
	{
		if(v[i]%2==0)
		{	v[k]=v[i];
			k++;
		}
		i++;
	}
	v.resize(k);
}

// 移动法
void delodd2(vector<int>&v)
{
	int k=0;
	int i=0;
	while(i<v.size())
	{
		if(v[i]%2==0)
			v[i-k]=v[i];	
		else
			k++;	
		i++;
	}
	v.resize(v.size()-k);
}

// 区间划分法
void delodd3(vector<int>&v)
{
	int k=-1;
	int i=0;
	while(i<v.size())
	{
		if(v[i]%2==0)
		{
			k++;	
			swap(v[k], v[i]);// 交换
		}
		i++;
	}
	v.resize(k+1);
}

// 打印信息
void disp(vector<int> &v)
{
	for(auto e:v)
		printf("%d ",e);
	printf("\n");
}
int main()
{
	vector<int>v={2,1,4,5,1,2};
	printf("v: "); disp(v);
	
	printf("删除奇元素之后：\n"); 
	
	delodd3(v);
	printf("v: "); disp(v);
	return 0;
}
